// run: $exce < input
#include <cstdio>

int const maxn = 100001;
int tree[maxn];
int stack[maxn];
int top, n;

int lowbit(int x) { return x & -x; }

void add(int pos, int value)
{
	for (; pos < maxn; pos += lowbit(pos)) tree[pos] += value;
}

int sum(int pos)
{
	int ret = 0;
	for (; pos > 0; pos -= lowbit(pos)) ret += tree[pos];
	return ret;
}

int find(int value)
{
	int l = 0, r = maxn - 1, mid, ret;
	while (l + 1 < r) {
		if ((l + r) & 1) mid = (l + r - 1) / 2;
		else mid = (l + r) / 2;
		ret = sum(mid);
		if (ret < value) l = mid;
		else r = mid;
	}
	return l + 1;
}

int main()
{
	char s[20];
	scanf("%d", &n);
	while (n--) {
		scanf("%s", s);
		if (s[1] == 'u') {
			int pos;
			scanf("%d", &pos);
			stack[++top] = pos;
			add(pos, 1);
		}
		else if (s[1] == 'o') {
			if (top == 0) { printf("Invalid\n"); continue; }
			int out = stack[top];
			add(out, -1);
			printf("%d\n", stack[top--]);
		} else if (s[1] == 'e') {
			if (top == 0) { printf("Invalid\n"); continue; }
			int ret = (top & 1) ? find((top+1)/2) : find(top/2);
			printf("%d\n", ret);
		} else
			printf("Invalid\n");
	}
}

